/*
提交链接：
1011. 在 D 天内送达包裹的能力-中等
完成日期：2024/9/13
二分搜索
*/

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        // 确定二分查找的范围
        // 最小值为包裹中最重的一个，因为船的运载能力必须至少能装下最重的包裹
        int low = *max_element(weights.begin(), weights.end());
        // 最大值为所有包裹的总重量，因为船的运载能力不能小于总重量
        int high = accumulate(weights.begin(), weights.end(), 0);
        // 进行二分查找，找到能够满足在 `days` 天内运输所有包裹的最小运载能力
        while (low < high) {
            // 计算中间值，即当前猜测的船运载能力
            int mid = low + (high - low) / 2;
            // 判断当前运载能力 `mid` 是否能够在 `days` 天内完成运输
            if (canShip(weights, days, mid)) {
                // 如果可以运输，尝试更小的运载能力
                high = mid; // 更新 `high` 为 `mid`
            } else {
                // 如果不可以运输，增加运载能力
                low = mid + 1; // 更新 `low` 为 `mid + 1`
            }
        }
        // 返回最小的能满足条件的运载能力
        return low;
    }
    
private:
    // 辅助函数：检查给定的运载能力 `capacity` 是否能够在 `days` 天内运输所有包裹
    bool canShip(const vector<int>& weights, int days, int capacity) {
        int currentWeight = 0; // 当前一天的重量
        int neededDays = 1; // 从第一天开始
        // 遍历每个包裹
        for (int weight : weights) {
            // 如果当前包裹的重量加上当前天的总重量超过了运载能力
            if (currentWeight + weight > capacity) {
                neededDays++; // 需要新的天数来运输当前包裹
                currentWeight = weight; // 当前天的重量重置为当前包裹的重量
                // 如果所需天数超过了 `days`，则运载能力不够
                if (neededDays > days) return false;
            } else {
                // 当前包裹可以放在当前天的剩余空间里
                currentWeight += weight;
            }
        }
        // 如果能够在给定的天数内完成运输，返回 true
        return true;
    }
};